import java.util.Arrays;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            List<Integer[]> twoResult = twoSum(nums, i+1, -nums[i]);
            for (Integer[] ints : twoResult) {
                List<Integer> resultItem = new ArrayList<>();
                resultItem.add(nums[i]);
                resultItem.add(ints[0]);
                resultItem.add(ints[1]);
                result.add(resultItem);
            }
        }
        return result;
    }

    public List<Integer[]> twoSum(int[] nums, int start, int target) {
        List<Integer[]> result = new ArrayList<>();
        int j = nums.length - 1;
        for (int i = start; i < j; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            while(i < j && nums[i] + nums[j] > target) {
                j--;
            }
            if (i < j && nums[i] + nums[j] == target) {
                result.add(new Integer[] {nums[i], nums[j]});
            }
        }
        return result;
    }
}